package leetcode_81_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class subsetsWithDup_90 {
    /**
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        /**
         * 思路是递增排序后，进行前后元素比较
         * 递归回溯
         */
        Arrays.sort(nums);
        ans.add(new ArrayList<>());
        function(nums,0);
        return ans;
    }
    List<Integer>combine=new ArrayList<>();
    List<List<Integer>>ans=new ArrayList<>();
    /**
     * 递归回溯求所有不重复的组合
     * @param i   当前递归起始数字
     */
    public void function(int[] nums,int i){
        //boolean isSame=false;
        if(i==nums.length){
            return;
        }
        for (int t = i; t < nums.length; t++) {
            //同一层递归中的遇到**循环中已遍历过**的上一个相同的元素，需要直接跳过，
            // 需要跳过循环第一个的比较，上一层递归会产生影响
            if(t!=i && nums[t]==nums[t-1])
                continue;
            combine.add(nums[t]);
            ans.add(new ArrayList<>(combine)); //每次往下经过一个节点，直接添加进结果集
            function(nums, t+1);
            combine.remove(combine.size()-1);
        }
    }
}
